package sort;

import util.Comparator;

/**
 * 不是基于比较的排序，只有存在进制的才可以使用
 * 稳定，因为数 到桶 是先入先出的，保证相等的值顺序不会乱
 *
 * @author Liaorun
 */
public class RadixSort implements Sortable {

    public static void main(String[] args) {
        // 这个算法只支持正数
        Comparator comparator = new Comparator(10, 10, true);
        comparator.start(new RadixSort());
    }

    @Override
    public void sort(int[] arr) {
        radixSort(arr);
    }

    @Override
    public void sort(int[] arr, int k) {

    }

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    private static void radixSort(int[] arr, int l, int r, int digit) {
        // 10 进制不能变
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] bucket = new int[r - l + 1];

        // 最大的数有几个10进制位就要循环几次
        for (int d = 1; d <= digit; d++) {
            // 10 个空间
            // count[0] 当前位（d位）是0的数字有多少个
            // count[1] 当前位（d位）是0和1的数字有多少个
            // count[2] 当前位（d位）是（0，1，2）的数字有多少个
            // count[i] 当前位（d位）是（0~i）的数字有多少个
            int[] count = new int[radix];

            for (i = l; i <= r; i++) {
                // 获取某个10进制位的值
                j = getDigit(arr[i], d);
                // 记录j出现的次数
                count[j]++;
            }

            // count中每个数记录了 j 出现的次数
            // 下面的循环将count记录的值改为 在该位10进制 <= j数字出现的次数
            // 就是count 中所有的值加上前面所有的数值
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 所有数字出桶放到了辅助数组
            for (i = r; i >= l; i--) {
                j = getDigit(arr[i], d);
                // 每一个数字区是从右向左放入
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }

            // 把辅助数组的值放到原数组
            for (i = l, j = 0; i <= r; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    /**
     * @param x 数
     * @param d 获取那个位置的值
     * @return 获取d位置的值
     */
    private static int getDigit(int x, int d) {
        // 相当于左移，把需要的位移到个位
        int y = x / ((int) Math.pow(10, d - 1));
        // 取模取出个位
        return y % 10;
    }

    /**
     * 返回一个数组中最大的数有几个10进制位
     *
     * @param arr 数组
     * @return 数组中最大的数有几个10进制位
     */
    private static int maxBits(int[] arr) {
        // 找出最大的数
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }
}
